package datastructure.tree;

/**
 *
 * @author Lei Zhang
 */
public class CheckBinaryTree {
  
  public static boolean isBinarySearchTree(TreeNode root, int min, int max) {

    if (root == null) {
      return true;
    } else if (root.left == null && root.right == null) {
      return true;
    } else if (root.left == null && root.right != null && root.right.value
        > min) {
      return isBinarySearchTree(root.right, max, root.right.value);
    } else if (root.right == null && root.left != null && root.left.value
        < max) {
      return isBinarySearchTree(root.left, root.left.value, max);
    } else if (root.left.value < max && root.right.value > min) {
      return isBinarySearchTree(root.left, min, root.left.value)
          && isBinarySearchTree(root.right, root.right.value, max);
    } else {
      return false;
    }
  }

  public static void main(String args[]) {

    TreeNode n1 = new TreeNode(1);
    TreeNode n2 = new TreeNode(2);
    TreeNode n3 = new TreeNode(3);
    TreeNode n4 = new TreeNode(4);
    TreeNode n5 = new TreeNode(5);
    TreeNode n6 = new TreeNode(6);

    n5.left = n2;
    n5.right = n6;

    n2.left = n1;
    n2.right = n4;

    n4.left = n3;

    System.out.println(CheckBinaryTree.isBinarySearchTree(n5, n5.value,
        n5.value));
  }
}
